#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<set>

using namespace std;


int merge(vector<int>& nums, int l, int r)
{
    if (l == r)  return 0;

    int mid = l + r >> 1;
    int ret = merge(nums, l, mid) + merge(nums, mid + 1, r);

    int i = l, j = mid + 1;
    while (i <= mid)
    {
        while (j <= r && (long long)nums[i] > 2 * (long long)nums[j])
            j++;
        ret += (j - mid - 1);
        i++;
    }

    vector<int> t(r - l + 1);
    i = l, j = mid + 1;
    int k = 0;
    while (i <= mid && j <= r)
    {
        if (nums[i] < nums[j])   t[k++] = nums[i++];
        else    t[k++] = nums[j++];
    }
    while (i <= mid) t[k++] = nums[i++];
    while (j <= r)   t[k++] = nums[j++];

    for (i = l, k = 0; i <= r; i++, k++)
        nums[i] = t[k];
    return ret;
}

int reversePairs(vector<int>& nums) {
    if (nums.size() == 0)    return 0;
    return merge(nums, 0, nums.size() - 1);
}

int main()
{
    vector<int> v = { 2,4,3,5,1 };
    cout << reversePairs(v);
    return 0;
}